package leetcode.array;

/**
 * @author 陈正龙
 * @date 2022/7/19 17:55
 * 二分查找
 */
public class _704 {

    /*
     * 给定一个 n 个元素有序的（升序）整型数组 nums 和一个目标值 target  ，
     * 写一个函数搜索 nums 中的 target，如果目标值存在返回下标，否则返回 -1。
     */

    /*
     *  示例1
     *  输入: nums = [-1,0,3,5,9,12], target = 9
     *  输出: 4
     *  解释: 9 出现在 nums 中并且下标为 4
     */

    /*
     *  示例2
     *  输入: nums = [-1,0,3,5,9,12], target = 2
     *  输出: -1
     *  解释: 2 不存在 nums 中因此返回 -1
     */

    /**
     * 注意区间的选取
     * 为什么是 middle-1  middle+1
     * 总结: 二分查找 middle每次要移动一下 否则会
     */
    public static void main(String[] args) {
        int[] nums = new int[]{-1,0,3,5,9,12};
        int search = search(nums, 9);
        System.out.println("search = " + search);
    }

    public static int search(int[] nums, int target) {
        if (target > nums[nums.length - 1] || target < nums[0]) {
            return -1;
        }
        int left = 0;
        int right = nums.length - 1;
        while (left <= right) {
            int middle = (right - left) / 2 + left;
            if (target > nums[middle]) {
                left = middle+1;
            } else if (target < nums[middle]) {
                right = middle-1;
            } else {
                return middle;
            }
        }
        return -1;
    }
}
